package com.xinwei.leetcode.二叉树;

import java.util.HashSet;

// https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
public class _105_从前序与中序遍历序列构造二叉树 {
    // 前序遍历可以得到根节点，从而可以通过根节点把中序遍历的结果分成两边，得到左右两边的数据就可以在前序遍历中分出左右子树的数据，从而得到子树的根节点。
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root = new TreeNode();
        root.val = preorder[0];
        int rootRoom = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == root.val) {
                rootRoom = i;
            }
        }
        HashSet<Integer> set = new HashSet<>();
        for (int i = inorder.length - 1; i > rootRoom; i--) {
            set.add(inorder[i]);
        }
        int rightRoom = 0;
        int j = preorder.length - 1;
        while (set.contains(preorder[j])) {
            rightRoom = j;
            j--;
        }
        return null;
    }

    private void buildChildTree(int rootIn, int leftBorderIn, int rightBorderIn, int[] preorder, int[] inorder, TreeNode root) {

    }
}
